#include<iostream>
#include<vector>
#include<stack>
#include<string>
#include<queue>
#include<algorithm>
#include<unordered_set>
using namespace std;


struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x):val(x), left(nullptr), right(nullptr){}
};

class Solution{
    private:
    vector<pair<int, int>> index;

    public:
    void ans1(vector<vector<string>>& board){
        int row = board.size();
        int col = board[0].size();
        
        int i = 0, j = 0;
        for(j = 0; j != col; j++){
            if(board[0][j] == "O"){
                dfs(board, 0, j);
            }
        }
        for(i = 1; i != row; i++){
            if(board[i][col-1] == "O"){
                dfs(board, i, col-1);
            }
        }
        for(j = col-2; j >= 0; j--){
            if(board[row-1][j] == "O"){
                dfs(board, row-1, j);
            }
        }
        for(i = row-2; i >= 1; i--){
            if(board[i][0] == "O"){
                dfs(board, i, 0);
            }
        }
        
        for(i = 0; i != row; i++){
            for(j = 0; j != col; j++){
                board[i][j] = "X";
            }
        }
        int len = index.size();
        for(i = 0; i != len; i++){
            board[index[i].first][index[i].second] = "O";
        }

    }

    //深度优先
    void dfs(vector<vector<string>>&grid, int r, int c){
        int row = grid.size();
        int col = grid[0].size();

        grid[r][c] = "X";
        index.push_back({r, c});
        if(r-1 >= 0 && grid[r-1][c] == "O"){
            dfs(grid, r-1, c);
        }
        if(r+1 < row && grid[r+1][c] == "O"){
            dfs(grid, r+1, c);
        }
        if(c-1 >= 0 && grid[r][c-1] == "O"){
            dfs(grid, r, c-1);
        }
        if(c+1 < col && grid[r][c+1] == "O"){
            dfs(grid, r, c+1);
        }
    }

};


void show(vector<vector<string>>& board){
    int row = board.size();
    int col = board[0].size();
    for(int i = 0; i != row; i++){
        for(int j = 0; j != col; j++){
            cout << board[i][j] << " " << ends;
        }
        cout << endl;
    }
}


void test1(){
    vector<vector<string>> grid = {
        {"X","X","X","X"},
        {"X","O","O","X"},
        {"X","X","O","X"},
        {"X","O","X","X"}
    };

    Solution s;
    s.ans1(grid);
    show(grid);
    
}

void test2(){
    vector<vector<string>> grid = {
        {"X"}
    };

    Solution s;
    s.ans1(grid);
    show(grid);
    
}



int main(void){
    test1();
    cout << "-----------------------------" << endl;
    test2();

    return 0;
}